In a data communication network, routing devices receive messages at one of a set of input interfaces and forward them on to one or more of a set of output interfaces. Users typically require that such routing devices operate as quickly as possible in order to keep pace with a high rate of incoming messages. In a packet routing network, where information messages are transmitted in discrete chunks or “packets” of data, each packet includes a header. A routing device uses the header information for routing the packet to an output interface for subsequent forwarding to a destination device. A routing device can forward the packet to another routing device for further processing and/or forwarding.
Header information used for routing can include destination and source addresses for the packet. Additionally, a routing device can use header information such as destination device port, source device port, protocol, packet length, and packet priority. Routing devices can use header information for access control, accounting, quality of service, or class of service.
FIG. 1 illustrates a generic packet routing device 100 such as that found in the prior art. Routing device 100 consists of a set of line cards 110 and a switching fabric 120. Each line card 110 includes an input interface 111, an output interface 112, a fabric interface 170, and a control element 130. Line cards 110 connect to communications network 1, which can be a local, enterprise, metropolitan, or wide-area network, through both input interface 111 and output interface 112. More than one input interface 111 or output interface 112 can be provided, with each interface carrying a fraction of the full capacity of control element 130.
Control element 130 is configured to receive inbound packets (i.e., packets entering the routing device from network 1) from input interface 111, process the packets, and transmit them through fabric interface 170 to switching fabric 120, which then sends the packets to another (or the same) line card 110 for further processing. This path to the switching fabric is the “receive” or ingress path into the routing device from the network.
Outbound packets (i.e., transmitted out of the routing device) are received from switching fabric 120 through fabric interface 170, processed in control element 130, and transmitted to network 1 on output interface 112. Accordingly, this path from the switching fabric is the “transmit” or egress path from the routing device to the network.
In the prior art, control element 130 can include an inbound packet receiver 140, lookup circuit 145, inbound memory controller 150, first memory 160, a second (outbound) lookup circuit 175, outbound memory controller 155, second memory 165, and outbound transmitter 180. Control circuits 190 are also provided to perform such tasks as configuration, initialization, statistics collection, and accounting functions, as well as to process certain exception packets.
In routing device 100, packets are received from the physical medium of the network at input interface 111. The inbound packet receiver 140 operates in conjunction with lookup circuit 145 to determine routing treatments for inbound packets. Lookup circuit 145 includes routing treatment information disposed in a memory structure. These routing treatments can include, for example, one or more of the following:                selection of one or more output interfaces to which to forward inbound packets responsive to the destination device, to the source and destination device, or to information in any other packet header fields (packets may also be dropped);        determination of access control list (ACL) treatment for inbound packets;        determination of class of service (COS) treatment for inbound packets;        determination of one or more accounting records or treatments for inbound packets; and        determination of other administrative treatment for inbound packets.        
One shortcoming of traditional prior art packet routing systems is an inability of processors using software to perform necessary lookup and queue management functions in real time (i.e., approaching line rate of the incoming packets). As the need for increased packet throughput grows, such software-based systems lack sufficient scalability to meet the demands of modern data communications networks.
Prior art packet routing systems tuned for additional speed with hardware implementation of functions once performed by software exhibit a drawback of a lack of flexibility. As the hardware is less able to be reconfigured without replacement or redesign, these prior art packet routing systems can be rendered obsolete by the adoption of new standards and communication protocols.
A further drawback of prior art routing systems is their relative inability to rapidly provide a range of services, such as bandwidth management, based on packet priority, as represented by, for example, the various fields in a packet header. Such systems are often described as providing type of service (TOS), quality of service (QOS), or class of service (COS). Such prior art routing systems typically experience additional packet latency and throughput reduction when performing services such as bandwidth management based on packet priority, if they are capable of performing these features at all. In particular, so-called “edge” QOS features associated with, for example, leased-line aggregation and content aggregation are in particular need of support by new routing devices.
What is therefore needed is a flexible routing system, preferably distributed on a line card, that provides ultra-high throughput packet switching and bandwidth management. The system architecture should be able to be reconfigured to handle a variety of network protocols and optimization. In particular, low-latency routing determined by individual packet class of service is desired. Such a line card should operate at near line rate (i.e., at or near the maximum speed of transmission over the physical medium and without any appreciable buffering delay).